home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Advanced I⁄O v2.3 / Advanced i⁄o / arithm_coding.cc next >
Text File  |  1995-05-29  |  8KB  |  255 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *                Arithmetic Coding
  6.  *
  7.  * The functions implemented here perform actual variable bit decoding/encoding
  8.  * of an item (an integer number) using the cumulative probabilities supplied
  9.  * by a particular model of the source data.
  10.  *
  11.  * $Id: arithm_coding.cc,v 2.0 1995/02/07 19:30:52 oleg Exp oleg $
  12.  *
  13.  ************************************************************************
  14.  */
  15.  
  16. #ifdef __GNUC__
  17. #pragma implementation "arithm.h"
  18. #endif
  19. #include "arithm.h"
  20.  
  21. /*
  22.  *------------------------------------------------------------------------
  23.  *               Constructors and Destructors
  24.  * Note, constructor doesn't yet know if encoding or decoding is to be 
  25.  * performed. Nor does it open the bit stream. You have to open the
  26.  * stream explicitly using the appropriate open() function (see class BitIO and
  27.  * EndianIO).
  28.  */
  29.  
  30.                 // Just initialize the data fields
  31. ArithmCodingData::ArithmCodingData(Input_Data_Model& model)
  32.     : Source_model(model)
  33. {
  34.   low  = 0;            // Start with the full code range
  35.   high = Top_value;
  36.   bits_to_follow = 0;        // Nothing to follow yet
  37.   value = 0;
  38.   assert( Half == 1<<(Code_size-1) && Third_qtr == Half | First_qtr );
  39.   Coding_status = Init;
  40. }
  41.  
  42.  
  43.                 // Initialization
  44. void ArithmCodingOut::initialize(void)
  45. {
  46.   Source_model.open((BitOut&)(*this));
  47.   Source_model.agree_on_top_freq( (1<<(Code_size-2)) - 1 );
  48.   Coding_status = Coding;
  49. }
  50.  
  51. void ArithmCodingIn::initialize(void)
  52. {
  53.   Source_model.open((BitIn&)(*this));
  54.   register int i;            // Read in the first code value
  55.   for(i=0; i<Code_size; i++)
  56.     value = (value << 1) | get_bit();;
  57.   Source_model.agree_on_top_freq( (1<<(Code_size-2)) - 1 );
  58.   Coding_status = Coding;
  59. }
  60.  
  61. /*
  62.  *------------------------------------------------------------------------
  63.  *            Handling the coded stream
  64.  */
  65.  
  66.                 // Close the coded stream
  67. void ArithmCodingOut::close(void)
  68. {
  69.   if( Coding_status == EoF )
  70.     return;                // Already closed
  71.   Coding_status = EoF;
  72.   encode_index(Source_model.eof_index());
  73.   done_encoding();
  74.   BitOut::close();
  75. }
  76.  
  77. void ArithmCodingIn::close(void)
  78. {
  79.   Coding_status = EoF;
  80.   BitIn::close();
  81. }
  82.  
  83.                 // Put a symbol into the coded stream
  84. void ArithmCodingOut::put(const Symbol symbol)
  85. {
  86.   Index index = Source_model.get_index(symbol);
  87.   encode_index(index);
  88.   Source_model.update_model(index);
  89. }
  90.  
  91. Symbol ArithmCodingIn::get(void)
  92. {
  93.   assure( Coding_status != EoF, "Cannot read past End-of-File" );
  94.   Index index = decode_index();
  95.   if( index == Source_model.eof_index() )
  96.   {
  97.     Coding_status = EoF;
  98.     return 0;
  99.   }
  100.                     // Note, update_model may change
  101.   Symbol symbol = Source_model.get_symbol(index);
  102.   Source_model.update_model(index);    // symbol vs. index mapping, that's why
  103.                     // get_symbol should precede update_mod
  104.   return symbol;
  105. }
  106.  
  107. /*
  108.  *------------------------------------------------------------------------
  109.  *               Encoding an item
  110.  */
  111.  
  112.                 // Output a bit following by
  113.                 // bits_to_follow opposite bits
  114. inline void ArithmCodingOut::put_bit_plus_follow(const char bit)
  115. {
  116. //  message("\nWrite 1 + %d bits",bits_to_follow);
  117.   put_bit(bit);
  118.   for(; bits_to_follow > 0; bits_to_follow--)
  119.     put_bit(!bit);            // The loop sets bits_to_follow to 0
  120. }
  121.  
  122. void ArithmCodingOut::encode_index(const Index index)
  123. {
  124.   Code range = high - low + 1;        // Current range
  125.                     // Narrow the code region to that
  126.                     // allotted to this symbol
  127.                     // First compute a new low end
  128.   low = low + (range * Source_model.cum_freq(index)) /
  129.           Source_model.total_cum_freq();
  130.                     // and add the new range to it
  131.   high = low + (range * Source_model.freq(index)) / 
  132.              Source_model.total_cum_freq() - 1;
  133.   if( high <= low )
  134.     _error("ArithmCoder went crazy: high <= low!\n"
  135.        "index = %d, symbol = %d, freq = %d, cum_freq = %d total = %d\n",
  136.        "range = %d (0x%6x), high = 0x%6x, low = 0x%6x",
  137.        index, index == Source_model.eof_index() ? 0 : 
  138.        Source_model.get_symbol(index),
  139.        Source_model.freq(index), Source_model.cum_freq(index), 
  140.        Source_model.total_cum_freq(), range, range, high, low);
  141.  
  142. #if 0
  143.   message("\n\n-----\nindex %d, symbol %d, freq %d, cum_freq %d",
  144.       index, index == Source_model.eof_index() ? 0 : 
  145.       Source_model.get_symbol(index), 
  146.       Source_model.freq(index), Source_model.cum_freq(index));
  147.   message("\nhigh %6x, low %6x", high, low);
  148. #endif
  149.  
  150.   for(;;)            // Loop to output bits we're positive about
  151.   {
  152.     if( !(high & Half) )/*high < Half*/ // If the region is entirely in low
  153.       put_bit_plus_follow(0);        // half, binary expansion starts w/ 0
  154.     else if( low & Half )     // low >= Half, since Top_value = 1<<Codesize-1
  155.     {                    // Upper half binary numbers begin
  156.       put_bit_plus_follow(1);        // positively with 1, so output it
  157.       low &= ~Half, high &= ~Half;    // Subtract the offset to top
  158.     }
  159.                 // if( low <= First_qtr && high < Third_qtr )
  160.     else if( low & First_qtr & (high ^ Third_qtr) ) 
  161.     {                    // Cannot tell the bit now, but
  162.       bits_to_follow++;            // the next bit would be opposite
  163.       low -= First_qtr, high -= First_qtr;    // Subtract offset to middle
  164.     }
  165.     else 
  166.       break;
  167.     low = low << 1;            // Scale up the range, shifting in
  168.     high = (high << 1) | 1;        // 1 as the LSB for high
  169.   }
  170. }
  171.  
  172.  
  173. /*
  174.  *------------------------------------------------------------------------
  175.  *            Finish encoding the stream
  176.  * Output two bits that select the quarter that contains the current 
  177.  * code range. Note that the decoder part of the codec analyzes bits when
  178.  * they are loaded into the 'value' variable, which acts like
  179.  * sort of the buffer. We're analyzing a couple of bits off the top of
  180.  * the buffer, shift them out and shift in some bits from the input stream.
  181.  * But if the input stream contains only, say, 2 bits that specify the
  182.  * termination, we still need to shift them on the top of the buffer. 
  183.  * I.e. we need to read up to Code_size-2 phony bits after the EOF (that's
  184.  * what has been suggested in the 'Text Compression' book).
  185.  * However, reading "past" actual EOF makes it impossible to concatenate
  186.  * two ArithmCoding streams (or write anything after the encoded stream
  187.  * for that matter). Instead of 'reading' phony bits after the EOF, 
  188.  * we'd rather write some extra bits.
  189.  * So, after the encoding is finished, we still need to output enough 
  190.  * 'phony' bits to prevent EOF on reading. On the other hand, we need
  191.  * to make sure that *all* these bits are going be read back on decoding.
  192.  */
  193.  
  194. void ArithmCodingOut::done_encoding(void)
  195. {
  196.   bits_to_follow += 1;
  197.   if( low < First_qtr )
  198.     put_bit_plus_follow(0);
  199.   else
  200.     put_bit_plus_follow(1);
  201.  
  202.   register int i;            // Output phony bits
  203.   for(i=0; i<Code_size-2; i++)
  204.     put_bit_plus_follow(0);
  205. }
  206.  
  207. /*
  208.  *------------------------------------------------------------------------
  209.  *            Decoding an item from the input stream
  210.  */
  211.  
  212. Index ArithmCodingIn::decode_index()
  213. {
  214.   Code range = high - low + 1;        // Current code region
  215.                     // Find the cumulative freq for the
  216.                     // symbol
  217.   Code cum = ((value-low+1)*Source_model.total_cum_freq() - 1) / 
  218.              range;
  219.   Index index = Source_model.find_index(cum);
  220.  
  221.                     // Narrow the code region to that
  222.                     // allotted to this symbol
  223.                     // First compute a new low end
  224.   low = low + (range * Source_model.cum_freq(index)) / 
  225.           Source_model.total_cum_freq();
  226.                     // and add the new range to it
  227.   high = low + (range * Source_model.freq(index)) / 
  228.            Source_model.total_cum_freq() - 1;
  229.   assert( high > low );
  230.  
  231.   for(;;)            // Simulate the encoder and get rid of bits
  232.   {                // encoder has put for 'index'
  233.     if( !(high & Half) )        // if( high < Half )
  234.       ;                    // Expand the low half of code region
  235.     else if( low & Half )        // if( low >= Half )
  236.     {                    // Expand the upper half
  237.       value &= ~Half;
  238.       low &= ~Half, high &= ~Half;
  239.     }
  240.     else if( low & First_qtr & (high ^ Third_qtr) ) 
  241.     {                // if( low >= First_qtr && high < Third_qtr )
  242.       value -= First_qtr;        // Expand middle half
  243.       low -= First_qtr, high -= First_qtr;
  244.     }
  245.     else
  246.       break;
  247.     low = low << 1;            // Scale up the range, shifting in
  248.     high = (high << 1) | 1;        // 1 as the LSB for high
  249.     value = (value << 1) | get_bit();;    // Move in the next input bit 
  250.   }
  251.  
  252.   return index;
  253. }
  254.  
  255.